\documentclass{ctexart}
\usepackage{listings}%插入代码
\usepackage{geometry}%设置页面大小边距等
\usepackage{authblk}%作者机构等信息
\usepackage{graphicx}%插入图片
\usepackage{url}%Bib中引用网页
\usepackage{amssymb}%为了用\mathbb
\usepackage{amsmath}%数学方程的显示
%\usepackage{amsthm}%数学定理
\usepackage{listings}%插入代码
\usepackage{fancyhdr}%设置页眉页脚
\usepackage{lastpage}%总页数
\usepackage{hyperref}%引用网页
\usepackage{float}
\usepackage{xcolor}
\usepackage{tikz}



\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}%一定要放在前面！
\pagestyle{fancy}%设置页眉页脚
\lhead{周游\ 3200106105}%页眉左
\chead{Numerical Analysis homwork03}%页眉中
\rhead{2022/10/18}%章节信息
\cfoot{\thepage/\pageref{LastPage}}%当前页，记得调用前文提到的宏包
\rfoot{浙江大学数学科学学院}
\renewcommand{\headrulewidth}{0.1mm}%页眉线宽，设为0可以去页眉线
\renewcommand{\footrulewidth}{0.1mm}%页脚线宽，设为0可以去页眉线
\setlength{\headwidth}{\textwidth}

\hypersetup{%设置网页链接颜色等
    colorlinks=true,%链接将会有颜色，默认是红色
    linkcolor=blue,%内部链接，那些由交叉引用生成的链接将会变为蓝色（blue）
    filecolor=magenta,%链接到本地文件的链接将会变为洋红色（magenta）
    urlcolor=blue,%链接到网站的链接将会变为蓝绿色（cyan）
    }

\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof:}
\newtheorem{solution}{Solution:}

\begin{document}
%\newpage
\section*{2.9.1 Theoretical questions}
\subsection*{\uppercase\expandafter{\romannumeral1}}
\begin{solution}
$p_1(f;x)$过点$(1,1),(2,\frac{1}{2})$
\begin{equation}
    p_1(f;x) = -\frac{1}{2}x+\frac{3}{2}
    \notag
\end{equation}
由于$f''(x)=\frac{2}{x^3}$，代入得
\begin{equation}
\begin{aligned}
    \xi(x) &= \sqrt[3]{\frac{(x-1)(x-2)}{\frac{1}{x}-(-\frac{1}{2}x+\frac{3}{2})}} = \sqrt[3]{2x}
\end{aligned}
    \notag
\end{equation}
\end{solution}

\begin{solution}
$\xi$延拓到$[1,2]$\ ,\ $max\xi=\sqrt[3]{4},min\xi=\sqrt[3]{2},maxf''(\xi)=1$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral2}}
\begin{solution}
首先，$\sum\limits_{i=0}^n f_i l_i (x) $满足$l_i(x_j) = \delta_{i j}$，令
$p(x) = \sum\limits_{i=0}^n f_i (l_i (x))^2$，即\\
\begin{equation*}
    p(x) = \sum\limits_{i=0}^n f_i (\prod\limits_{k=0 \atop k\neq i}^n\frac{x-x_k}{x_i-x_k})^2
\end{equation*}
则$p(x) \geqslant 0 , \ 
p \in P^+_{2n}, \ and \ p(x_i) = f_i$ 。
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral3}}
\begin{solution}
    $f(x) = e^t$ , 
when n = 0, $f[t] = e^t$,\\
when n = 1, $f[t,t+1] = (e-1)e^t$ \\
assume it's true when k < n (n > 1)， i.e. 
$f[t,t+1,\cdots , t+k] = \frac{(e-1)^k}{k!}e^t$\\
when k = n, \\
\begin{equation}
\begin{aligned}
    f[t,t+1,\cdots , t+n] &= \frac{f[t+1,\cdots , t+n]-f[t,\cdots , t+n-1]}{(t+n)-t} \\
    &= \frac{1}{n}[\frac{(e-1)^{n-1}}{(n-1)!}e^{t+1}-\frac{(e-1)^{n-1}}{(n-1)!}e^{t}] \\
    &= \frac{(e-1)^n}{n!}e^t\\
\end{aligned}
    \notag
\end{equation}
By induction, the proposition is true.
\end{solution}
\begin{solution}
    Let t = 0 , since $f^{(n)}(x) = e^x$
    \begin{equation*}
        f[0,1,\cdots,n] = \frac{(e-1)^n}{n!} = \frac{1}{n!}f^{(n)}(\xi) = \frac{1}{n!}e^{\xi}
    \end{equation*}
    Then 
    \begin{equation*}
        \xi = n \ln (e-1) > \frac{n}{2}
    \end{equation*}
    So $\xi$ is located on the right of $\frac{n}{2}$ . 
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral4}}
\begin{solution}
f(x) 取值如下:\\
\begin{table}[H]
    \begin{center}
    \begin{tabular}{l|c|c|c|r} 
      x & 0 & 1 & 3 & 4\\
      \hline
      f(x) & 5 & 3 & 5 & 12\\
    \end{tabular}
    \end{center}
\end{table}
Newton formula : \\
\begin{table}[H]
    \begin{center}
    \begin{tabular}{l|c c c r} 
      0 & 5 &  &  & \\
      1 & 3 & -2 &  & \\
      3 & 5 & 1 & 1 & \\
      4 & 12 & 7 & 2 & $\frac{1}{4}$\\
    \end{tabular}
    \end{center}
\end{table}
$p_3(f;x) = 5 - 2x + x(x-1) + \frac{1}{4} x (x-1) (x-3) = \frac{1}{4}x^3 - \frac{9}{4}x$+ 5
\end{solution}

\begin{solution}
$p'(x) = \frac{3}{4}x^2-\frac{9}{4}$， $p'(x)$在$(1,\sqrt{3})$上小于0，在$(\sqrt{3},3)$上大于0，\\
$x_{min}=\sqrt{3}\approx 1.73$， $p(x_{min})\approx 2.40$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral5}}
\begin{solution}
$f(x) = x^7, f'(x) = 7x^6, f''(x) = 42x^5$\\
\begin{table}[h!]
    \begin{center}
    \begin{tabular}{l|c c c c c r} 
      0 & 0 \\
      1 & 1 & 1 &  & \\
      1 & 1 & 7 & 6 & \\
      1 & 1 & 7 & 21 & 15 \\
      2 & 128 & 127 & 120 & 99 & 42 \\
      2 & 128 & 448 & 321 & 201 & 102 & 30\\
    \end{tabular}
    \end{center}
\end{table}
\\
$f[0,1,1,1,2,2] = 30$
\end{solution}

\begin{solution}
    The 5th derivative of f is : 
    \begin{equation*}
        f^{(5)}(x) = 2520x^2
    \end{equation*}
    since
    \begin{equation*}
        f[0,1,1,1,2,2] = \frac{1}{5!}f^{(5)}(\xi) = 21\xi^2
    \end{equation*}
    so 
    \begin{equation*}
        \xi = \sqrt{\frac{10}{7}} \approx 1.195
    \end{equation*}
    
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral6}}
\begin{solution}
    By Hermite interpolation (table below): \\
    \begin{table}[h!]
    \begin{center}
    \begin{tabular}{l|c c c c r} 
      0 & 1 \\
      1 & 2 & 1 1  & \\
      1 & 2 & -1 & -2 & \\
      3 & 0 & -1 & 0 & $\frac{2}{3}$ \\
      3 & 0 & 0 & $\frac{1}{2}$ & $\frac{1}{4}$ & -$\frac{5}{36}$ \\
    \end{tabular}
    \label{key1}
    \end{center}
    \end{table}
$p(x) = 1 + x - 2x(x-1) + \frac{2}{3}x(x-1)^2 - \frac{5}{36}x(x-1)^2(x-3)$ \\
$f(2) \approx p(2) = \frac{11}{18} \approx 0.611 $
\end{solution}

\begin{solution}
    N = 2 + 1 + 1 = 4, 
    \begin{equation*}
        \begin{aligned}
            |R_4(f;2)| &= \frac{|f^{(5)}(\xi)}{(N+1)!}(2-0)(2-1)^2(2-3)^2\\
            &= \frac{|f^{(5)}(\xi)}{5!}\cdot 2 
            \leqslant \frac{2M}{5!}
            = \frac{M}{60}
        \end{aligned}
    \end{equation*}
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral7}}
\begin{solution}
    when k = 1, 
    \begin{equation*}
        \begin{aligned}
            \Delta f(x) &= f(x+h) - f(x) = hf[x_0,x_1]\\
            \nabla f(x) &= f(x) - f(x-h) = hf[x_0,x_{-1}]
        \end{aligned}
    \end{equation*}
    assume it's true when $k \leqslant n , n \in N^*$, consider k = n + 1\\
    \begin{equation*}
        \begin{aligned}
            \Delta^{n+1} f(x) &= \Delta\Delta^n f(x)\\
            &= \Delta f(x+h) - \Delta f(x) \\
            &= n!h^n f[x_1,\cdots,x_{n+1}]-n!h^n f[x_0,\cdots,x_n]\\
            &= (n+1)!h^{n+1}\frac{f[x_1,\cdots,x_{n+1}]- f[x_0,\cdots,x_n]}{x_{n+1}-x_0}\\
            &= (n+1)!h^{n+1}f[x_0,\cdots ,x_{n+1}]\\
            \end{aligned}
    \end{equation*}
由归纳法知对所有n,结论成立。对$\nabla^{n+1}f(x)$同理。    
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral8}}
\begin{solution}
    \begin{equation*}
        \begin{aligned}
            \frac{\partial}{\partial x_0}f[x_0,x_1,\cdots ,x_n]
            &= \lim\limits_{h\rightarrow 0}\frac{f[x_0+h,x_1,\cdots,x_n]-f[x_0,x_1,\cdots ,x_n]}{(x_0+h)-x_0}\\
            &= \lim\limits_{h\rightarrow 0}\frac{f[x_1,\cdots,x_n,x_0+h]-f[x_0,x_1,\cdots ,x_n]}{(x_0+h)-x_0}\\
            &= \lim\limits_{h\rightarrow 0}f[x_0,x_1,\cdots ,x_n,x_0+h]\\
            &= \lim\limits_{h\rightarrow 0}f[x_0,x_0+h,x_1,\cdots ,x_n]\\
            &= f[x_0,x_0,x_1,\cdots ,x_n] \ \ (\text{if continue})
        \end{aligned}
    \end{equation*}
    只要证明$f[x_0,x,x_1,\cdots ,x_n]$在$x_0$处关于$x$连续。\\
    当 n = 0 时，
    \begin{equation*}
        \begin{aligned}
            \lim\limits_{x\rightarrow x_0}f[x_0,x] = \lim\limits_{x\rightarrow x_0}\frac{f(x)-f(x_0)}{x-x_0} 
            = f'(x_0) = f[x_0,x_0]
        \end{aligned}
    \end{equation*}
    假设 $k \leqslant n (n \geqslant 0)$ 时连续性成立，考虑$k = n + 1$时: \\
    \begin{equation*}
        \begin{aligned}
            \lim\limits_{x\rightarrow x_0}f[x_0,x,x_1,\cdots ,x_{n+1}] 
            &= \lim\limits_{x\rightarrow x_0}\frac{f[x_0,x,x_2,\cdots ,x_{n+1}]-f[x_0,x,x_1,\cdots ,x_{n}]}{x_{n+1}-x_1} \\
            &= \frac{f[x_0,x_0,x_2,\cdots ,x_{n+1}]-f[x_0,x_0,x_1,\cdots ,x_{n}]}{x_{n+1}-x_1}\\
            &= f[x_0,x_0,x_1,\cdots ,x_{n+1}]
        \end{aligned}
    \end{equation*}
    由归纳法知对所有n，连续性得证，结论成立。\\
    other : $\frac{\partial}{\partial x_i}f[x_0,x_1,\cdots ,x_n] = f[x_0,\cdots ,x_{i-1},x_i,x_i,x_{i+1},\cdots ,x_n]$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral9}}
\begin{solution}
    由Chebyshev定理，任意首项系数为1的$p_n(x)$，$\mathop{\max}_{x\in [-1,1]}|p(x)| \geqslant \frac{1}{2^{n-1}}$\\
    Let $y = -1 + 2\cdot \frac{x-a}{b-a} = \frac{2x - a - b}{b - a} \in [-1,1]$，then $x = \frac{1}{2}[(b-a)y + a + b] \in [a,b]$，代入得
    \begin{equation*}
        \begin{aligned}
            \text{原式} &= \mathop{\min}\mathop{\max}_{y \in [-1,1]}|b_0 y^n + b_1 y^{n-1} + \cdots + b_n | \\
            &= \mathop{\min}|b_0|\mathop{\max}_{y \in [-1,1]} |y^n + \frac{b_1}{b_0}y^{n-1} + \cdots + \frac{b_n}{b_0} |
            \geqslant \frac{|b_0|}{2^{n-1}}
        \end{aligned}
    \end{equation*}
    其中$b_0 = a_0(\frac{b-a}{2})^n$， 故原式最小值为$\frac{|a_0|(b-a)^n}{2^{2n-1}}$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral10}}
\begin{solution}
    $T_n = \cos(n \arccos{x}) \in \mathbb{P}_n$, Assume $\exists \  p \in \  \mathbb{P}_n^a , \ s.t. \ ||\hat{p}_n(x)||_{\infty} > ||p||_{\infty}$\\
    Let $Q(x) = \hat{p}_n(x) - p(x) \in \mathbb{P}_n$, $Q(a) = 0$, since $x_k' = \cos{\frac{k \pi}{n}}$ 是 $\hat{p}_n(x)$ 的n+1个正负交错的极值点
    \begin{equation*}
        Q(x_k') = \hat{p}_n(x_k') - p(x_k') \in \mathbb{P}_n \ , \ \ k =0,1,\cdots , n
    \end{equation*}
    由于$||\hat{p}_n(x)||_{\infty} > ||p||_{\infty}$，故Q在[-1,1]上有n个零点。由a>0也是Q的零点，故Q由n+1个不同零点，故$Q(X)=0$，$p(x)=\hat{p}_n(x)$。与$||\hat{p}_n(x)||_{\infty} > ||p||_{\infty}$矛盾
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral11}}
\begin{solution}
    $b_{n,k}(t) = \binom{n}{k}t^k(1-t)^{n-k} , \ \forall k = 0,1,\cdots,n, \ \forall t \in (0,1)$
    obviously $b_{n,k}(t) > 0$\\
    \begin{equation*}
        \sum\limits_{k = 0}^n b_{n,k}(t) = \binom{n}{k}t^k(1-t)^{n-k} = (t+1-t)^n = 1
    \end{equation*}
Consider $\sum\limits_{k=0}^n\binom{n}{k}p^k q^{n-k} = (p+q)^n , \ p + q = 1$, derive on p : 
\begin{equation}
    \sum\limits_{k=0}^n k \binom{n}{k}p^{k-1}q^{n-k} = n(p+q)^{n-1}    
    \label{11.1}
\end{equation}
multiple p on both side : 
\begin{equation}
    \sum\limits_{k=0}^n k \binom{n}{k}p^{k}q^{n-k} = n p(p+q)^{n-1}
    \label{11.2}
\end{equation}
Let p = t , q = 1-t : 
\begin{equation}
    \sum\limits_{k=0}^nk \binom{n}{k}t^k (1-t)^{n-k} = n t
    \label{11.3}
\end{equation}
Then (2.50c) is proved
\end{solution}

\begin{solution}
    When n = 1 , it's trival. Consider n > 1 , in (\ref{11.2}) derive on p : 
    \begin{equation}
        \sum\limits_{k=0}^n k^2 \binom{n}{k}p^{k-1}q^{n-k} = n (p+q)^{n-1} + n(n-1)p(p+q)^{n-2}
    \end{equation}
    multiple p on both side : 
    \begin{equation}
        \sum\limits_{k=0}^n k^2 \binom{n}{k}p^{k}q^{n-k} = n p(p+q)^{n-1} + n(n-1)p^2(p+q)^{n-2}
    \end{equation}
    let p = t , q = 1-t : 
    \begin{equation}
        \sum\limits_{k=0}^n k^2 \binom{n}{k}t^{k}(1-t)^{n-k} = n t + n(n-1)t^2
    \end{equation}
    so 
    \begin{equation}
        \begin{aligned}
            \sum\limits_{k=0}^n (k-nt)^2 \binom{n}{k}t^{k}(1-t)^{n-k} 
            &= \sum\limits_{k=0}^n (k^2-2knt+n^2t^2) \binom{n}{k}t^{k}(1-t)^{n-k} \\
            &= \sum\limits_{k=0}^n k^2 b_{n,k}(t) - 2nt \sum\limits_{k=0}^n k b_{n,k}(t) + n^2t^2\sum\limits_{k=0}^n b_{n,k}(t)\\
            &= n t + n(n-1)t^2 - 2nt \cdot nt + n^2t^2\\
            &= nt(1-t)
        \end{aligned}
    \end{equation}
    Then (2.50d) is proved
\end{solution}

\end{document} 